/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhongfang
 *
 */
public class GenerateParentheses {
	static ArrayList<String> allList=new ArrayList<>();
	private static void geneAStr(StringBuilder input,int i,int eCount,int mCount,int n) {//递归生成合法字符串
		StringBuilder stringBuilder=new StringBuilder(input);
		if(eCount==n){//只能生成右括号
			while (stringBuilder.length()<2*n) {
				stringBuilder.append(')');
			}
			allList.add(stringBuilder.toString());
			return;
		}
		String s="";
		String[] strings=s.split("");
		if(mCount==0){//只能生成左括号
			stringBuilder.append('(');
			//递归到下一个
			geneAStr(stringBuilder, i+1, eCount+1, mCount+1, n);
			return;
		}
		StringBuilder stringBuilder2=new StringBuilder(stringBuilder);
		stringBuilder2.append('(');
		geneAStr(stringBuilder2, i+1, eCount+1, mCount+1, n);//填写左括号
		if(mCount>0){
			StringBuilder stringBuilder3=new StringBuilder(stringBuilder);	
			stringBuilder3.append(')');//填写右括号
			geneAStr(stringBuilder3, i+1, eCount, mCount-1, n);//填写右括号
		}
	}
    public static List<String> generateParenthesis(int n) {
        StringBuilder stringBuilder=new StringBuilder("(");
        geneAStr(stringBuilder, 1, 1, 1, n);
        return allList;
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		generateParenthesis(3);
		System.out.println(allList);
	}

}
